#include<iostream>
#include<cstring>
using namespace std;
const int N=1e3+10;
struct node
{
    int vi;//体积
    int wi;//价值
}nums[N];
int Value[N][N];

int main()
{
	int n,v;cin>>n>>v;
    for(int i=1;i<=n;i++)
    {
        cin>>nums[i].vi>>nums[i].wi;
    }
	//每样物品无限，求这个背包至多能装多大价值的物品？

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=v;j++)
		{
			Value[i][j]=Value[i-1][j];
			if(nums[i].vi<=j)
			{
				Value[i][j]=max(Value[i][j],
					Value[i][j-nums[i].vi]+nums[i].wi);
			}
		}
	}
	cout<<Value[n][v]<<endl;

	//若背包恰好装满，求至多能装多大价值的物品？
	memset(Value,-1,sizeof(Value));
	for(int i=0;i<=n;i++)
	{
		Value[i][0]=0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=v;j++)
		{
			Value[i][j]=Value[i-1][j];
			if(nums[i].vi<=j&&Value[i][j-nums[i].vi]!=-1)
			{
				Value[i][j]=max(Value[i][j],
					Value[i][j-nums[i].vi]+nums[i].wi);
			}
		}
	}
	cout<<(Value[n][v]==-1?0:Value[n][v])<<endl;
}